/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mirac
 * Date: 2025-09-01
 * Time: 18:06
 */
public class Sort {

    //归并排序_递归实现
    public static void mergeSort(int[] arr) {
        mergeSortTmp(arr,0,arr.length - 1);
    }
    private static void mergeSortTmp(int[] arr,int left,int right) {
        if (left >= right) {
            return;
        }
        //进行分解
        int mid = (right + left)/2;
        mergeSortTmp(arr,left,mid);
        mergeSortTmp(arr,mid + 1,right);
        //到这里意味着分解完毕

        //开始合并
        merge(arr,left,mid,right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int[] tmp = new int[right - left + 1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;
        //将两个子数组从小到大放到tmp中
        while (s1 <= e1 && s2 <= e2) {
            if (arr[s1] <= arr[s2]) {
                tmp[k++] = arr[s1++];
            }else {
                tmp[k++] = arr[s2++];
            }
        }
        //如果第一个子数组还有
        while (s1 <= e1) {
            tmp[k++] = arr[s1++];
        }
        //如果第二个子数组还有
        while (s2 <= e2) {
            tmp[k++] = arr[s2++];
        }

        for (int i = 0; i < k; i++) {
            arr[i + left] =  tmp[i];
        }
    }

    //归并排序_非递归实现
    public static void mergeSortNor(int[] arr) {
        int gap = 1;
        while (gap < arr.length) {
            for (int i = 0; i < arr.length; i += gap*2) {
                int left = i;
                int mid = left + gap - 1;
                if(mid >= arr.length) {
                    mid = arr.length-1;
                }
                int right = mid + gap;
                if(right >= arr.length) {
                    right = arr.length-1;
                }
                merge(arr,left,mid,right);
            }
            gap *= 2;
        }
    }

    //计数排序
    public static void countSort(int[] arr) {
        int maxVal = arr[0];
        int minVal = arr[0];
        //找出数组中的最大值和最小值
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > maxVal) {
                maxVal = arr[i];
            }
            if (arr[i] < minVal) {
                minVal = arr[i];
            }
        }
        //创建计数数组
        int[] count = new int[maxVal - minVal + 1];

        //进行计数
        for (int i = 0; i < arr.length; i++) {
            int index = arr[i];
            count[index - minVal]++;
        }

        //根据计数数组对原数组进行排序
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] != 0) {
                arr[index] = i + minVal;
                index++;
                count[i]--;
            }
        }
    }
}
